package com.xucy.springboot.common.BalanceTree;

/**
 * @Author xucy
 * @Date 2019-04-18 10:02
 * @Description
 **/

public class Node {

    int value;
    Node leftNode;
    Node rightNode;

    public  Node(int value){
        this.value=value;
    }

    /**
     * 添加节点
     *
     * @Author xucy
     * @Date 10:48 2019-04-18
     * @param
     * @return
     */
    public  void addNode(Node node){
        Node oldNode=this;
        Node newNode=node;

        if(value>node.value){
            if(this.leftNode!=null){
                newNode=this.leftNode;
                newNode.addNode(node);
            }else{
                this.leftNode=node;
            }

        }

        if(value<node.value){
            if(this.rightNode!=null){
                newNode=this.rightNode;
                newNode.addNode(node);
            }else{
                this.rightNode=node;
            }

        }

        //查询是否是平衡
        if(leftNode!=null &&rightNode!=null && this.leftNode.height()-this.rightNode.height()>=2){
            //进行右旋转
            //进行双旋转(当左子树自己都不满足平衡二叉树时进行左子树双旋转)
            if(leftNode!=null && leftNode.leftNode.height()-leftNode.rightNode.height()>=2){
                leftNode.leftRotate();

                //进行右旋转
                rightRotate();
            }else{
                //进行右旋转
                rightRotate();
            }

        }
        if(leftNode!=null &&rightNode!=null && this.rightNode.height()-this.leftNode.height()>=2){
            //进行左旋转
            leftRotate();

            //进行左旋转
            //进行双旋转(当右子树自己都不满足平衡二叉树时进行左子树双旋转)
            if(rightNode!=null && rightNode.rightNode.height()-rightNode.leftNode.height()>=2){
                rightNode.rightRotate();

                //进行左旋转
                leftRotate();
            }else{
                //进行左旋转
                leftRotate();
            }
        }

    }

    //进行右旋转
    private void rightRotate() {
        //1.先创建一个新的节点，值等于当前节点的值
        Node newRight=new Node(value);
        //2.把新节点的右子树设置为当前节点的右子树
        newRight.rightNode=rightNode;
        //3.把新节点的左子树设置为当前节点的左子树的右子树
        newRight.leftNode=leftNode.rightNode;
        //4.把当前节点的值替换为左子树的值
        value=leftNode.value;
        //5.把当前节点的左子树设置为左子树的左子树
        leftNode=leftNode.leftNode;
        //6.把当前节点的右子树设置为新节点
        rightNode=newRight;
    }
    //进行左旋转
    private void leftRotate() {
        //1.先创建一个新的节点，值等于当前节点的值
        Node newRight=new Node(value);
        //2.把新节点的左子树设置为当前节点的左子树
        newRight.leftNode=leftNode;
        //3.把新节点的右子树设置为当前节点的右子树的左子树
        newRight.rightNode=rightNode.leftNode;
        //4.把当前节点的值替换为右子树的值
        value=rightNode.value;
        //5.把当前节点的右子树设置为右子树的右子树
        rightNode=rightNode.rightNode;
        //6.把当前节点的右子树设置为新节点
        leftNode=newRight;
    }

    //返回树的高度
    public int height(){
        int i=Math.max(leftNode==null?0:leftNode.height(),rightNode==null?0:rightNode.height())+1;
        return i;
    }

    //中序遍历
    public static  void midSort(Node node){

        if(node.leftNode!=null){
            midSort(node.leftNode);
        }

        System.out.println(node.value);

        if(node.rightNode!=null){
            midSort(node.rightNode);
        }



    }

    /**
     * 查找节点
     *
     * @Author xucy
     * @Date 10:51 2019-04-18
     * @param
     * @return
     */
    public Node search(int val){

        if(this.value==val){
            return this;
        }else if(this.value<val){
            if(this.rightNode!=null){
                return  this.rightNode.search(val);
            }else{
                return null;
            }
        }else if(this.value>val){
            if(this.leftNode!=null){
                return this.leftNode.search(val);
            }else{
                return null;
            }
        }
        return null;
    }

    /**
     * 删除节点
     *
     * @Author xucy
     * @Date 10:49 2019-04-18
     * @param
     * @return
     */
    public  void deleteNode(int  val){
        Node searchNode=search(val);
        if(searchNode==null){
            return;
        }else{
            //找到他的父节点
            Node parent=searchParent(val);
            //删除的节点是叶子节点
            if(searchNode.leftNode==null&& searchNode.rightNode==null){
                if(parent.leftNode.value==val){
                    parent.leftNode=null;
                }else{
                    parent.rightNode=null;
                }
                //删除节点有两个子节点
            }else if(searchNode.rightNode!=null && searchNode.leftNode!=null){
                    //删除右子树中最小的节点，获取到该节点的值
                    int min =deleteMin(searchNode.rightNode);
                    searchNode.value=min;

            }else{
                //删除节点有一个节点，判断是有父节点的右节点 还是有左节点
                if(parent.leftNode.value==val){
                    //判断删除节点有左节点还是右节点
                    if(searchNode.leftNode!=null){
                        parent.leftNode=searchNode.leftNode;
                    }else{
                        parent.leftNode=searchNode.rightNode;
                    }
                }else{
                    if(searchNode.leftNode!=null){
                        parent.rightNode=searchNode.leftNode;
                    }else{
                        parent.rightNode=searchNode.rightNode;
                    }
                }

            }
        }
    }

    //删除右子树中最小的节点，获取到该节点的值
    private int deleteMin(Node node) {
        //找到最小的节点
        Node target=node;
        while (target.leftNode!=null){
            target=target.leftNode;
        }

        //删除最小节点，如果最小节点有右节点 ，则右节点不删除，上升到最小节点位置
        deleteNode(target.value);

        return target.value;
    }

    //找到他的父节点
    public Node searchParent(int val){
        if(leftNode.value==val||rightNode.value==val){
            return this;
        }else{
            if(value>val){
                return leftNode.searchParent(val);
            }else{
                return rightNode.searchParent(val);
            }
        }

    }
}
